1. Field of the Invention
The present invention relates generally to the data processing field, and more particularly, to a method for balancing a binary search tree.
2. Description of the Related Art
A binary search tree is a data structure for representing tables and lists so that items in the tables or lists can be easily accessed, added and deleted. A binary search tree contains a set of the items in a particular table or list, with one item per node of the tree. The items are arranged on the tree in a symmetric order. For example, if a node x of the tree contains a specific item i, the left sub-tree of x will contain items less than item i, and the right sub-tree will contain items greater than item i.
When a binary search tree becomes unbalanced, the time required to do a look-up can increase significantly. For example, a project that may require only seconds to complete using a balanced tree may require minutes or even hours to complete with an unbalanced tree. As a result, balancing a binary search tree is an important and pervasive problem, and many solutions have been proposed over the years. In general, however, the proposed solutions are non-optimal in that they often perform differently on different workloads and frequently introduce significant overhead.
One mechanism for improving efficiency in balancing a binary search tree is to use a self-adjusting data structure in which a restructuring rule is applied during each operation in order to improve the efficiency of future operations. The publication “Self Adjusting Binary Search Trees”, Daniel Dominic Sleator and Robert Endre Tarjan, Journal of the Association for Computing Machinery, Vol. 32, No. 3, July, 1985, pp. 652-686, hereinafter referred to as “Sleator”, describes a self-adjusting form of binary search tree referred to as a “splay” tree. The heuristic used in restructuring a splay tree is referred to as “splaying”, and involves balancing a tree by moving an accessed node to the root of the tree by performing a sequence of rotations bottom-up along a path from the node to the root. The “bottom-up splaying process” is described in detail in the publication.
Sleator also recognizes that a possible drawback of splaying is that the process requires a large amount of restructuring; and, thus, significantly increases overhead. Sleator therefore proposes modifying the restructuring rules of the splaying process to move the accessed node only part way to the root. This balancing process is referred to as “bottom-up semisplaying”, and has the effect of reducing the depth of every node on the access path to, at most, about half of its previous value. Although bottom-up semisplaying can provide a reduction in overhead as compared to splaying, it is still computationally intensive.
There is, accordingly, a need for a mechanism for balancing a binary search tree that is effective in substantially all environments, and that reduces the overhead involved in balancing a tree.